iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 4
0
自我挑戰組

資料結構大便當系列 第 4

[Day 4] Hashtable,練習做一張表格

  • 分享至 

  • xImage
  •  

Hash table 雜湊表,一個 key-value 的資料結構,能根據給予的 key 以 O(1) 時間找出 value
Hash table 會有一個 hash function,其 function 計算出鍵值,並將 value 映射到表中一個位置,透過這樣的儲存與取值方式加速。
而在 C++ 中,又有 4個容易搞混的東西:map, set, unordered_map, unordered_set
其中 map 與 set 是透過紅黑樹建構而成,unordered_map 與 unordered_set 才是 hash table。
而 unordered_set 只有 key,並沒有 value。


例題:217. Contains Duplicate
直接使用 leetcode easy 的題目結束這一回合

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        
        // 建立一個 key 跟 value 皆為 int 的 hash table
        unordered_map<int, int> m;
        
        // 將數組加入 hash table
        for (auto v : nums)
            ++m[v];
        
        // 如果 second(value) 超過 1 個,則表示存在 "Duplicate"
        for (auto p : m) {
            if (p.second > 1) {
                return true;
            }
        }
        return false;
    }
};

上一篇
[Day 3] String,從字元陣列到類別
下一篇
[Day 5] Sets 集合
系列文
資料結構大便當30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言